Resolving-power dominating sets

Title: Resolving-power dominating sets
Creator: Stephen, Sudeep; Rajan, Bharati; Grigorious, Cyriac; William, Albert
Relation: Applied Mathematics and Computation Vol. 256, p. 778-785
Publisher Link: http://dx.doi.org/10.1016/j.amc.2015.01.037
Publisher: Elsevier
Resource Type: journal article
Date: 2015
Description: For a graph G(V,E) that models a facility or a multi-processor network, detection devices can be placed at vertices so as to identify the location of an intruder such as a thief or fire or saboteur or a faulty processor. Resolving-power dominating sets are of interest in electric networks when the latter helps in the detection of an intruder/fault at a vertex. We define a set S⊆V to be a resolving-power dominating set of G if it is resolving as well as a power-dominating set. The minimum cardinality of S is called resolving-power domination number. In this paper, we show that the problem is NP-complete for arbitrary graphs and that it remains NP-complete even when restricted to bipartite graphs. We provide lower bounds for the resolving-power domination number for trees and identify classes of trees that attain the lower bound. We also solve the problem for complete binary trees.
Subject: domination; power domination; metric domination
Identifier: http://hdl.handle.net/1959.13/1336435
Identifier: uon:27616
Identifier: ISSN:0096-3003
Language: eng
Reviewed

		Thumbnail	File	Description	Size	Format